package bintree.leetcode;

//236. 二叉树的最近公共祖先

public class Num236_lowestCommonAncestor {
    private TreeNode goalNode;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        findNode(root,p,q);
        return goalNode;
    }

    private boolean findNode(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return false;
        }

        int left = findNode(root.left,p,q)?1:0;
        int right = findNode(root.right,p,q)?1:0;
        int mid = (root == p || root == q)?1:0;

        if(left+right+mid == 2){
            goalNode = root;
        }
        return (left+right+mid) > 0;
    }
}
